#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACK_INCREATMENT 10
#define MAX_SIZE 6
typedef int Status;
typedef char SElemType;

// 相比小驼峰法，大驼峰法（即帕斯卡命名法）把第一个单词的首字母也大写了。常用于类名，属性，命名空间等
// 变量一般用小驼峰法标识。驼峰法的意思是：除第一个单词之外，其他单词首字母大写。

int count = 0;

// 树的数据结构的定义
typedef struct BinNode
{
    SElemType data; // 存放数据
    struct BinNode *left_Child, *right_Child;
} BinNode, *BinTree;

/*实现函数:
三序遍历，
初始化树的节点,
获取树的深度,
先序插入数值,构建树
*/
Status init_tree_node(BinTree node)
{
    node->left_Child = NULL;
    node->right_Child = NULL;
    return OK;
}

//不使用二重指针将无法修改树的值导致无法复制(错误代码如下)
// Status creat_tree(BinTree node, char *data)
// {
//     if (count >= 21) // 判断元素是否全部录入,21是数组长度
//     {
//         return OK;
//     }

//     if (data[count] == ' ')
//     {
//         count++;
//         node = NULL;
//     }
//     else
//     {
//         if (node == NULL)
//         {
//             node = (BinTree)malloc(sizeof(BinNode));
//             node->left_Child = NULL;
//             node->right_Child = NULL;
//         }
//         node->data = data[count++];
//         creat_tree(node->left_Child, data);
//         creat_tree(node->right_Child, data);
//     }
//     return OK;
// }

Status creat_tree(BinTree *node, char *data) // 构造树[node是一个二重指针,*node指向一个树的根节点]
{
    if (count >= 21) // 判断元素是否全部录入,21是数组长度
    {
        return OK;
    }

    if (data[count] == ' ')
    {
        count++;
        *node = NULL;
    }
    else
    {
        if (*node == NULL)
        {
            *node = (BinTree)malloc(sizeof(BinNode));
            init_tree_node(*node);
        }
        (*node)->data = data[count++];
        creat_tree(&((*node)->left_Child), data);
        creat_tree(&((*node)->right_Child), data);
    }
    return OK;
}

Status visit(BinTree node) // 对每个元素的操作[这里是输出值]
{
    if (node == NULL)
    {
        return ERROR;
    }
    putchar(node->data);
    return OK;
}

Status PreorderTraverse(BinTree node, Status (*visit)(BinTree node)) // 先序遍历输出
{
    // 递归先序遍历
    if (node != NULL)
    {
        visit(node);
        PreorderTraverse(node->left_Child, visit);
        PreorderTraverse(node->right_Child, visit);
    }
    else
    {
        return OK;
    }
}

Status InorderTraverse(BinTree node, Status (*visit)(BinTree node)) // 中序遍历输出
{
    if (node != NULL)
    {
        InorderTraverse(node->left_Child, visit);
        visit(node);
        InorderTraverse(node->right_Child, visit);
    }
    else
    {
        return OK;
    }
}

Status PostorderTraverse(BinTree node, Status (*visit)(BinTree node)) // 后序遍历输出
{
    if (node != NULL)
    {
        PostorderTraverse(node->left_Child, visit);
        PostorderTraverse(node->right_Child, visit);
        visit(node);
    }
    else
    {
        return OK;
    }
}


int maxDepth(BinTree root)
{
    if (root == NULL)
        return 0;
    else
    {
        int x, y;
        x = maxDepth(root->left_Child);
        y = maxDepth(root->right_Child);
        return (x > y ? x : y) + 1;
    }
}

int main()
{
    BinTree root = (BinTree)malloc(sizeof(BinNode));
    init_tree_node(root);
    char data[21] = {'-', '+', 'a', ' ', ' ', '*', 'b', ' ', ' ', '-', 'c', ' ', ' ', 'd', ' ', ' ', '/', 'e', ' ', ' ', 'f'};

    // 输出存入的数据
    for (int i = 0; i < 21; ++i)
    {
        // printf("%d ",data[i]);
        putchar(data[i]);
    }
    creat_tree(&root, data);

    // 先序遍历输出
    printf("\n先序遍历输出:");
    PreorderTraverse(root, visit);

    // 中序遍历输出
    printf("\n中序遍历输出:");
    InorderTraverse(root, visit);

    // 后序遍历输出
    printf("\n后序遍历输出:");
    PostorderTraverse(root, visit);

    int depth = maxDepth(root);
    printf("\n最大深度:%d ", depth);
    return 0;
}